APUNTES MATEMATICA DISCRETA

Unidad 1: Logica

Tablas

Operaciones Logicas

Presedencia de Operadores

Tabla de Leyes Logicas

Nota: Cuando nos presentan un razonamiento hay dos tipos de razonamientos categoricos y no categoricos. En los categoricos las premisas tienen cuantificadores $(\forall x: , \exist x:)$ y por lo tanto definir un conjunto universal e.g: $U=\{x/\text{``} x \text{ es un auto''}\}$, las premisas son funciones e.g: $p(x) = \text{``}x \text{ es verde''}$, por ultimo, en el caso de que un razonamiento categorico sea invalido la forma de justificar que es invalido es definiendo un conjuto que demuestre la contradiccion del argumento.

Caso contrario son los no categoricos, en este caso las premisas no tienen cuantificadores, tampoco hay que definir un conjunto universal.

Reglas de Inferencia

Reglas de Inferecia Razonamientos Categoricos (CON CUANTIFICADORES):

$$p\rArr q\begin{cases} \neg q\rArr\neg p\\ \end{cases}$$

Unidad 2.1: Conjuntos

Propiedades de la inclusion

$X \subseteq Y \Leftrightarrow \forall a: a \in X \rArr a \in Y$

1. $\forall A: A \subseteq A. \text{ Todo conjunto esta incluido en si mismo.}$
2. $\forall A: \empty \subseteq A. \text{ El vacio esta incluido en todo conjuto.}$
3. $\forall A: A \subseteq U. \text{ Todo conjunto esta includo en el Universal.}$
4. $\forall A, B, C: A \subseteq B \land B \subseteq C \rArr A \subseteq C. \text{ Propiedad Transitiva.}$

Operaciones entre conjuntos

Propiedades de las Operaciones

$\phantom{hola}$

Conjunto de Partes

$P(A) = {X/ X \subseteq A}$

$X \in P(A) \Leftrightarrow X \subseteq A$

• Definicion: Dado un conjuto A, se define como conjuto de Partes de A al conjunto formado por todos los subconjuntos de A. Se denota como $P(A)$, e.g: $A = {1,2} P(A) = { \empty, \{1\}, \{2\}, A }$.

ACLARACIONES:

• $|P(A)| = 2^{|A|}$
• $P(\empty) = {\empty} (2^0 = 1 \therefore |P(\empty)| = 1 )$

Particion de un conjunto

• Definicion: Sea un cojunto $A \neq \empty$. Sea $P = { A_1, A_2, A_3,\dotsc, A_n}$, P es una particion si:
  • $A_i \neq \empty \text{ } \forall i$
  • $A_i \cap A_j = \empty \forall i \neq j$
  • $\cup A_i = A$

continuara?...

Producto Cartesiano

• Definicion: Dados dos conjuntos A y B, llamamos producto cartesiano de A por B al conjunto: $A \times B = { (x;y)/ x \in A \land x \in B }$

• El producto cartesiano esta formado por pares ordenados.

• Justamente como son pares ordenados, no es conmutativa, es decir, $A \times B \neq B \times A, \text{porque } (x;y) \neq (y;x).$

Propiedades del producto cartesiano

Demostraciones

En un caso de demostracion se compone de la siguiente manera, se tiene una o varias hipotesis y una sola tesis, LAS HIPOTESIS SE CONSIDERAN CIERTAS, y es gracias a esto que vamos a poder reemplazar alguna expresion de la tesis por una de la hipotesis

Caso particular: Si tengo que demostrar una igualdad ( $=$ ) debo hacer la demostracion en ambos sentidos, es decir, partir desde el miembro izquierdo, desarrollar hasta llegar al derecho y viceversa. EN ALGUNOS CASOS, las propiedades se pueden aplicar en ambos sentidos, pero esto no siempre se cumple, para esos casos solo queda volver a empezar el desarrollo desde cero.

Demostraciones con Partes de Conjuntos

Cuando se tiene que demostrar algo que involucre partes de un conjunto, se trabaja de la misma manera que con conjuntos, solo que ahora los elementos de P($A$) (siendo $A$ un conjunto o subconjunto generico) van a ser otros conjuntos. Esto es poruqe $P(A)$ nos devuelve otro conjunto... pero de mas conjuntos.

En vez de representar un elemento del conjunto como $\forall x: x \in A$ sera de esta forma $\forall X: X \in A$. Notese la diferencia que ahora el elemento generico del conjunto es otro conjunto.

Ademas, a la hora de reemplazar partes de un conjunto, se habla de un conjunto generico que esta incluido en este supuesto conjunto.

E.g: $P(A) \rArr \forall X: X \in P(A) \rArr X \subseteq A$

El resto de la demostracion deberia ser identica que con conjuntos.

Unidad 2.2: Induccion

PIC (Principio de Induccion Completa)

1. $v[ p(1) ] = V$   Paso base.
2. $v[ p(h) ] = V \rArr v[ p(h+1) ] = V$   Paso inductivo.

Aclaraciones:

• Paso Base: En el paso base lo que se busca es demostrar que la proposicion es verdadera evaluada en 1, si este no cumple con el paso base entonces la proposicion es falsa.

• Paso Inductivo: El paso inductivo es el planteo de un condicional, si cumple con un elemento generico "$h$" entonces cumplira con el siguiente a ese elemento inductivo "$h+1$".

  Este condicional se divide en dos partes, antecedente y consecuente, pero en este caso lo llamaremos hipotesis inductiva al antecedente y tesis inductiva al consecuente.

• La induccion solo aplica a proposiciones que trabajen en el conjunto de los elementos naturales.

Herramientas

Pares e Impares

$\phantom{hola}$

$\phantom{hola}$

$\phantom{hola}$

Binomio de Newton

Binomio de simplificado (h+1)

Numeros Primos

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

Algunas recomendaciones

• En ejercicios de divisiblilidad quiza convenga descomponer algun numero en la suma o resta de dos numeros, la idea es que alguno de estos dos sea multiplo del numero que se busca
  • Puede llegar a suceder que en algn caso tenga que evaluar si $h$ es impar o par, para evaluar si se puede hacer un factor comun o algo del estilo hasta llegar al multiplo que se busca.
  • Si se tiene una suma de potencias lo mejor es tratar de descomponer la suma del exponente (si es que hay).
• En ejercicios de inecuaciones es bastante complicado poder desarrollar el ejercicio, lo que se recomienda es usar la logica y reemplazar por valores relacionados de alguna forma con la hipotesis.
  • en general estos tienen una limitacion para $n$ por ejemplo $n\geq5$ en este caso se sabe que n tiene que ser mayor o igual que 5, esto nos sirve para reemplazarlo en alguna expresion.
  • En casos raros puede que tengas que reemplazar un termino por otro completamente distinto, mientras que se mantenga la desigualdad, vale. Recordar que siempre el objetivo es llegar a una expresion relacionada con nuestra tesis.
• En ejercicios de sumatoria es necesario "sacarnos" la sumatoria de en medio, para esto podemos descomponer la sumatoria en una suma de la sumatoria y otra expresion.

$\phantom{hola}$

$\phantom{hola}$

$\phantom{hola}$ $\phantom{hola}$

Unidad 3: Divisibilidad

• Se trabaja en el conjunto $\Z$

Division entera

Dados dos numeros $D$ y $d$, con $d\neq0$, existen y son unicos otros dos enteros $c$ y $r$ tales que: $D=c\cdot d+r$ y $0\le r \le \lvert d\rvert$

• En divisiones de Dividendo negativo es provable que al cociente le tenga que sumar 1 al numero que usaria de costubre porque el resto no puede ser negativo.

Si $d>0$:

$$c =\text{ent} \left(\frac{D}{d}\right) \land r = \text{mant} \left(\frac{D}{d}\right)\cdot d$$

Si $d<0$:

$$d^\prime = -d \rArr c^\prime = \text{ent}\left(\frac{D}{d^\prime}\right) \land r^\prime = \text{mant}\left( \frac{D}{d^\prime} \right)$$

Luego:

$$c = c^\prime \land r = r^\prime$$

• Si el divisor el negativo entonces lo que se debe hacer es

  1. Cambiar el signo al divisor (osea ahora es positivo)+
  2. Obtener el cociente y resto
  3. Cambiar de signo al cociente, el resto queda igual

• Si el cociente es resultado de $D/d$ es negativo el cociente se trunca hacia ariba, osea si es -39.78 el cociente sera -40

• De lo contrario si el resultado de $D/d$ el cociente se trunca hacia abajo $\lfloor$

Relacion de Divisibilidad

Sean: $a,b \in \Z:$

$$a\vert b \iff \exist k \in \Z / b = k \cdot a$$

$\phantom{hola}$

$\phantom{hola}$

Propiedades

1. $\forall a \in \Z: a\vert a$

   Dem:

   $$\forall a \in \Z: a=a\cdot 1 \land 1\in\Z \rArr a\vert a$$

2. $\forall a,b,c \in \Z: a\vert b \land b\vert c \rArr a\vert c$

   Dem:

   $$\forall a,b,c \in \Z: a\vert b \land b\vert c \rArr ^{(1)} b=a\cdot k \land c=b\cdot t\rArr c = (a\cdot k) \cdot t\rArr c=a\cdot (k\cdot t) \rArr a\vert c$$

   $(1): k,t \in \Z$

3. $\forall a,b,c \in \Z: a\vert b \land a\vert c \rArr a\vert (b+c)$

   Dem:

   $$\forall a,b,c \in \Z: a\vert b \land a\vert c \rArr b =a\cdot k \land c=a\cdot q \\ \rArr b+c = a\cdot k + a\cdot q\rArr b+c = a\cdot (k+q)\rArr a\vert (b+c)$$

4. $\forall a,b,c \in \Z: a\vert b \rArr a\vert (b\cdot c)$

   Dem:

   $$\forall a,b,c \in \Z: b=a\cdot k \rArr b\cdot c = (a\cdot k)\cdot c\rArr b\cdot c = a\cdot(k\cdot c)\rArr a\vert (b\cdot c)$$

Numeros Primos

• Numeros Primos: Son los numeros enteros positivso mayores que $1$, que solo son divisibles por $1, -1, n, -n$

• Propiedad:

  Sean, $p,a,b\in \Z:$ Si $n\vert a\cdot b \land p:\text{primo}\rArr n\vert a \lor n\vert b$

Teorema Fundamental de la Aritmetica

• Todo numero entero es o bien primo o se puede escribir como producto de factores primos de manera unica salvo el orden

$$n=p_1^{k_1}\cdot p_2^{k_2}\cdot \ldots \cdot p_r^{k_r}$$

Esto es la wea de factorear...

Minimo comun Multiplo (M.C.M)

• Proceso para obtener el m.c.m de cualquier numero:

  1. Descomponer los numeros en sus factores primos.
  2. Buscar todos los factores que aparezcan y si hay repetidos quedarse con el de mayor exponete.

$\phantom{hola}$

$\phantom{hola}$

Maximo comun Divisor (M.C.D)

• Proceso para obtener el m.c.d de cualquier numero:

  1. Descomponer los numeros en sus factores primos.
  2. Buscar los factores en comun y quedarse con el factor de menor exponente.

• Propiedad:

  $mcm(a,b) \cdot mcd(a,b) = \lvert a\cdot b\rvert$

  $d=\text{mcd}(a,b) \rArr d=s\cdot a+t\cdot b\text{ con s,t}\in\Z$

Algoritmmo de Euclides

El algoritmo de euclides se usa para calcular el maximo comun divisor (mcd) entre dos numeros, pero ademas se utiliza para expresarlos como combinacion lineal.

Propiedad:

Dados dos enteros $a$ y $b$, el $\text{mcd}(a,b) = \text{mcd}(b,r)$ siendo $r$ el resto de la division de $a$ por $b$.

• Dem:

  Dado un conjunto: $D_{a,b}=\{ x\in \Z/ x\vert a \land x\vert b \}$

$$\text{Demostrar: } D_{a,b} \subseteq D_{b,r} \\ \forall x \in D_{a,b} \rArr x\vert a \land x\vert b \rArr x\vert b\cdot q+r \land x\vert b \land x\vert b \\ \rArr x\vert b\cdot q+r \land x\vert b\cdot(-q) \land x\vert b \\ x\vert b\cdot q + r + b\cdot (-q) \land x\vert b \\ x\vert r \land x\vert b \rArr x\in D_{b,r}$$

• Pasos del algoritmo de euclides:
  1. Se dividen los numeros (el mas chico divide al mas grande)
  2. Se obtiene el cociente y el resto
  3. Luego el resto divide al divisor previo
  4. Se repite el proceso hasta que el resto valga 0.
  5. EL resto llega a 0 el resto prevo sera el mcd entre los dos numeros.

Algoritmo de Euclides de Forma Matricial

Siendo: $mcd(a,b) = n$

$$n = k_1 \cdot a + k_2 \cdot b$$

Ej: Calcular mcd $(720,224)$

$\phantom{hola}$

$\phantom{hola}$

$\phantom{hola}$

$\phantom{hola}$

$\phantom{hola}$

Ahora tomo la anteultima fila, en ella estaran los valores que necesito:

mcd$(720,224) = 16$

$16 = 5\cdot 720 + (-16)\cdot 224$

A la hora de completar la matriz trabajar siempre con valores positivos para evitar errores, pero si se cambia de signo algun numero recordar cambiarle el signo tambien al numero que multiplique a dicho numero que se cambio el signo.

Teorema de Bezout

Dados dos enteros $a$ y $b$:

$$\text{mcd}(a,b) = 1 \iff 1 = s\cdot a + t\cdot b \text{ con } s,t\in\Z$$

Esto solo sucede si y solo si el mcd$(a,b) = 1$.

• Dos numeros son coprimos si el mcd$(a,b)=1$
• Dos numeros son coprimos si s combinacion lineal da 1
• Por el teorema de Bezout dos numeros consecutivos siempre son coprimos

Algunas recomendaciones

• TENER MUY EN CUENTA QUE SE ESTA TRABAJANDO EN $\mathbf{Z}$, POR LO TANTO LOS NUMEROS NEGATIVOS TAMBIEN CUENTAN.

• En ejercicios de divisibilidad van a expresar una division con palabras. El primer paso es entenderla, luego nos van a dar otra division distinta, pero que hace uso de la primera. La clave esta en tratar de expresar toda esta nueva expresio como una division del caracter que nos estan pidiendo.

• Tener en cuenta la propiedad de Bezout

  • Este al ser un bicondicional se cumple en ambos sentidos, es decir si cumple con mcd = 1 tambie cumple con la combinacion lineal.

• Si el mcd entre dos numeros me da un numero $d$ este se puede expresar como combinacion lineal, pero si una combinacion lineal da un numero d, este no necesariamente es el mcd entre dos numeros.

• Como obtener todos los divisores de un numero:

  1. Descomponer a un numero en sus factores primos
  2. Para saber cuantos divisores son, a cada exponente se le suma 1 y despues se multiplican entre si. Eso da la cantidad de divisores.
  3. Luego armar la cuadricula con todas las combinaciones

Unidad 4: Relaciones

Definiciones

Dados dos conjuntos $A$ y $B$, llamamos relacion de $A$ en $B$ a cualquier subconjunto de $A\times B$

$R:A\to B$ $R$ es una relacion de $A$ en $B$. $(R\sube A\times B)$ es cualquier subconjunto incluido en el producto cartesiano.

• $R$ al ser un conjunto se puede representar igual que los conjuntos:

  • Por extension
  • Por Diagrama de Venn
  • Tablas
  • Graficos cartesianos (son diagramas de ejes con un punto en donde hay una relacion)

• Dominio de una Relacion:

  Sea $R: A\to B: \text{Dom}(R) = \{x \in A/\exists y \in B \land (x;y)\in R \}$

• Imagen de una Relacion:

  Sea $R: A\to B: \text{Im}(R) = \{y \in B/\exists x \in A \land (x;y)\in R \}$

• Relacion Inversa o Reciproca:

  Sea $R: A\to B: R^{-1}=\{ (y;x) \in B\times A / (x;y) \in R\}$

• Imagen de un Elemento:

  Sea $a\in A: \text{Im}(a) = \{ y\in B/(a;y)\in R \}$

• Relacion Complementaria

  Sea $R:A\to B: \bar{R}=\{ (x;y)\in A\times B/ (x;y)\notin R \} = A\times B - R$

• Funcion

  Sea $F:A\to B$

  $F$ es funcion si y solo si:

  • Existencia: $\forall x\in A: \exist y\in B: (x;y)\in F$

  • Unicidad: $\forall x\in A: \forall y_1, y_2\in B: \forall (x;y_1)\in F \land (x;y_2)\in F\rArr y_1=y_2$

  • Clasificacion de Funciones:

    • Funcion Inyectiva:

      $\forall x_1,x_2\in A,\forall y\in B: F(x_1)=y \land F(x_2)=y \rArr x_1=x_2$

    • Funcion Sobreyectiva:

      $\forall y\in B: \exist x\in A \land F(x)=y$

    • Funcion Biyectiva: Inyectiva $\land$ Sobreyectiva

    • Para que una funcion sea biyectiva los cardinales del conjunto de partida como el de llegada deben ser iguales.

Operaciones entre Matrices

1. Suma Logica o Disyuncion ($\lor$):

   $A\lor B = C$ Donde $A\in\{0,1\}^{n\times m}, B\in\{0,1\}^{n\times m}, C\in\{0,1\}^{n\times m}$.

   $\forall i: 1\ldots n: \forall j: 1\ldots m: c_{ij} =a_{ij} \lor b_{ij}$

2. Producto Logico o Conjunsion ($\land$):

   $A\land B = C$ Donde $A\in\{0,1\}^{n\times m}, B\in\{0,1\}^{n\times m}, C\in\{0,1\}^{n\times m}$.

   $\forall i: 1\ldots n: \forall j: 1\ldots m: c_{ij} =a_{ij} \land b_{ij}$

3. Producto Matricial Booleano ($\bullet$):

   $A\cdot B = C$ Donde $A\in\{0,1\}^{n\times m}, B\in\{0,1\}^{m\times p}, C\in\{0,1\}^{n\times p}$.

   $$$$

   $$$$

   $A^t = B$ Donde $A\in\{0,1\}^{n\times m}, B\in\{0,1\}^{n\times m}$.

   $\forall i: 1\ldots n: \forall j: 1\ldots m: b_{ij} =a_{ji}$

4. Complemento de una matriz:

   $\bar{A} = B$ Donde $A\in\{0,1\}^{n\times m}, B\in\{0,1\}^{n\times m}$.

   $\forall i: 1\ldots n: \forall j: 1\ldots m: b_{ij} = \neg{a_{ij}}$

Propiedades de Matrices

Comparacion de Matrices

Sean $A,B\in \{ 0,1\}^{n\times m}$

$$A<B \Leftrightarrow a_{ij}<b_{ij} \forall i, \forall j$$

$$A\leq B \Leftrightarrow a_{ij}\leq b_{ij} \forall i, \forall j$$

• En una matriz que es menor o igual que otra lo unico que importa es que en la matriz que es menor si tiene un $1$, es necesario que en la otra tambien haya un $1$

Matriz de una Relacion

Sea $R:A\to B$ con $A=\{ a_1,a_2,\ldots,a_n \} \text{ y } B=\{ b_1,b_2,\ldots,b_n \}$

$$M_R \in \{0,1\}^{n\times m} \begin{cases} 1 & \text{ si }(a_i,b_j)\in R \\ 0 & \text{ si }(a_i,b_j)\notin R \end{cases}$$

Operaciones con Matrices

Sean $R:A\to B$ y $S:A\to B$

Sea $M_R$ la matriz de $R$ y $M_S$ la matriz de $S$

$$M_{R \cup S} = M_R \lor M_S \\ M_{R \cap S} = M_R \land M_S \\ M_R^{-1}= (M_R)^t \\ M_{\overline{R}} = \overline{(M_R)}$$

Composicion de Relaciones

Dadas $R:A\to B$ y $S:B\to C$

$$S\circ R=\{(x,z)\in A\times C/ \exist y\in B \land (x,y)\in R \land (y,z)\in S \}$$

Para hacer composicion de matrices hay que hacer el producto matricial entre las matrices, el resultado sera la matriz de la relacion compuesta. Se tiene que respetar el orden.

$$M_{S\circ R}= M_R \cdot M_S$$

Relaciones Binarias

Son todas las relaciones que conjunto de partida es igual al de llegada $R:A\to A$.

Ej: $R:A\to A \text{ tal que }R=\{ (x,y) \in A\times A/y=x^2 \}$

$\phantom{hola}$

$\phantom{hola}$

$\phantom{hola}$

$\phantom{hola}$

$\phantom{hola}$

$\phantom{hola}$

$\phantom{hola}$

$\phantom{hola}$

$\phantom{hola}$

Propiedades de las Relaciones

Sea una relacion binaria $R:A\to A:$

• $R$ es Reflexiva $\Leftrightarrow \forall a\in A: (a,a) \in R$
  • En un diagrama de Venn tiene que haber bucles en todos los elementos
  • En forma matricial la diagonal principal tiene que estar llena de 1.
  • $I\leq M(R)$
• $R$ es A-Reflexiva $\Leftrightarrow \forall a\in A: (a,a) \notin R$
  • En un diagrama de Venn NO tiene que haber bucles en todos los elementos.
  • En forma matricial la diagonal principal tiene que estar llena de 0.
  • $I\land M(R) = N$
• $R$ es Simetrica $\Leftrightarrow \forall a,b\in A: (a,b)\in R\rArr (b,a)\in R$
  • En un diagrama de Venn si un elemento se relaciona con otro, este tanbien se debe relacionar con el primero.
  • Todos los $1$ que esten de un lado de la diagonal principal, tambien deben estar del otro.
  • $M(R) = M(R)^t$.
• $R$ es Asimetrica $\Leftrightarrow \forall a,b\in A: (a,b)\in R\rArr (b,a)\notin R$
  • En un diagrama de Venn si un elemento se relaciona con otro, este NO SE debe relacionar con el primero. Osea ni bucles ni caminos de ida y vuelta.
  • Todos los $1$ que esten de un lado de la diagonal principal, NO deben estar del otro.
  • $M(R) \land M(R)^t = N$.
• $R$ es Antisimetrica $\Leftrightarrow \forall a,b\in A: (a,b)\in R \land (b,a)\in R \rArr a=b$
  • En un diagrama de Venn si un elemento se relaciona con otro, este NO SE debe relacionar con el primero. En este caso si hay bucles pero no caminos de ida y vuelta.
  • Todos los $1$ que esten de un lado de la diagonal principal, NO deben estar del otro, a exepcion de la diagonal principal.
  • $M(R) \land M(R)^t \leq I$.
• $R$ es Transitiva $\Leftrightarrow \forall a,b,c\in A: (a,b)\in R \land (b,c)\in R \rArr (a,c)\in R$
  • En un diagrama de Venn si dos elementos (o mas) estan relacionados, entonces tienen que estar todas las relaciones posibles.
  • La una forma de verificar esta propiedad es haciendo el producto matricial y verificar que los unos que esten en el resultado esten en la matriz original (lo que dice la propiedad).
  • $M(R)\cdot M(R)\leq M(R)$.
• A transitiva es lo opuesto a la transitivia

Orden de evaluacion

1. Es reflexiva?
2. Es a-reflexiva?
3. Es simetrica?
4. Es a-simetrica?
5. Es antisimetrica?
6. Es transitiva?

Nota: Cuando son elementos finitos lo mejor es realizar la matriz, pero cuando son elementos infinitos tendremos que recurrir a la defincion.

Relacion de Conectividad

$\text{Sea } R:A\to A$            $R^2 = R\circ R$

$\text{En }R:x\to y\to z$      $\text{En }R^2 = x\to z$

En otras palabras la matris de $R^2$ nos devuelve todas las relaciones cuyos caminos son de longitud $2$. Esto tambien sucede para cualquier potencia $n$, nos devuelve todos los caminos de longitud $n$.

$$xR^ny\Leftrightarrow \text{exite un camino de longitud } n \text{ entre } x \text{ e } y$$

Relacion de Equivalencia

$$R:A\to A \text{ es de quivalencia si es} \begin{cases} \text{Reflexiva} \\ \text{Simetrica}\\ \text{Transitiva} \end{cases}$$

A las relaciones de quivalencia se las suele representar por el simbolo ~

Clase de Equivalencia

$$\text{Sea } (A;\text{\textasciitilde{}}) \text{\quad} \overline{a} = [a] = Cl(a)=\{ x\in A/ x \text{\textasciitilde{}}a \}$$

Conjunto de Clases

$$\text{Sea } (A;\text{\textasciitilde{}}) \text{\quad} A/\text{\textasciitilde{}} = \{ Cl(a)/ a\in A \}$$

Propiedades de las Clases de Equivalencia

Aclaracion 1: Las siguientes propiedades son validas porque se parte de que es una relacion de equivalencia, es decir, ya esta demostrado que la relacion es de equivalencia.

Aclaracion 2: Es lo mismo decir $Cl(a)$ que $[a]$

Consideremos $R$ relacion de equivalencia definida en un conjunto $A$

• Proiedad 1: $\forall a\in A:[a]\neq \varnothing$
  • Dem: Como se cumple la propiedad reflexiva de $R$ en $A$: $$\\ \forall a\in A: aRa\rArr a\in [a]\rArr [a]\neq \varnothing$$
• Propiedad 2: $\text{Si }a\in [b]\rArr b\in [a]$
  • Dem: $\text{Si }a\in [b]\rArr aRb \text{ (por def. de clase de Eq.)}\\\rArr bRa \text{ (por la prop. simetrica)}\\\rArr b\in [a]\text{ (por def. de clase de Eq.)}$
• Propiedad 3: Las clases de equivalencia son disjuntas "Dos a dos."
  • Basicamente que las clase no se intersectan, y si lo hacen deben ser identicas

Teorema Fundamental de las Relaciones de Equivalencia

Toda relacion de equivalencia definida en un conjunto, provoca en el mismo una particion (conjunto cociente)"

Reciprocamente, toda particion de un conjunto induce en el mismo una relacion de equivalecia.

$\text{Relacion de Equivalencia} \iff \text{Particion del conjunto}$

Basicamente cada relacion de equivalencia me determina una particion del conjunto (recordar definicion de particion). Y si hay una particion dentro del conjunto es porque hay una relacion de equivalencia que lo determina.

Demostracion del teorema

Toda relacion de equivalencia definida en un conjunto, provoca en el mismo una particion (conjunto cociente)"

Propiedades que debe cumplir:

1. $Cl(x) \neq \varnothing$
2. $Cl(x) \cap Cl(y) = \varnothing \quad (\text{si }Cl(x)\neq Cl(y))$
3. $\cup Cl(x) = A$

Dem: $\forall x\in A:x\in Cl(x) \text{ por reflexividad} \rArr x\in\cup Cl(x)$

Reciprocamente, toda particion de un conjunto induce en el mismo una relacion de equivalecia.

Por hipotesis $P=\{ A_1,A_2,A_3,\ldots,A_n \}$ es una particion de A.

Deinimos en $A: xRy \Leftrightarrow\exist A_i \in P:x\in A_i\land y\in A_j )$

1. Reflexiva: $\forall x\in A: x\in A_i (3^\text{ra}\text{ cond de particion})\\\rArr^{\text{idempot.}}x\in A_i\land x\in A_i\rArr xRx$

2. Simetrica: $\forall x,y\in A: xRy\rArr\exist A_i\in P: x\in A_i\land y\in A_i\\\rArr^{\text{conmutativ.}} \exist A_i\in P: y\in A_i\land x\in A_i\rArr yRx$

3. Transitiva: $\forall x,y,z\in A: xRy\land yRz\\\rArr [\exist A_i\in P:x\in A_i\land y\in A_i]\land[\exist A_k\in P:y\in A_k\land z\in A_k]\\\rArr A_i = A_k (2^\text{da}\text{ prop de particion})\\\rArr\exist A_i\in P: x\in A_i\land z\in A_i\rArr xRz$

Aclaraciones:

• NO partir de la tesis a la hora de demostrar las propiedades de una relacion de equivalencia.

  • En el caso de la propiedad reflexiva, se parte de la hipotesis que un elemento generico que pertenece al conjunto, y luego se llega a la reflexiva

• Alguas propiedades de la igualdad que sirven para demostrar las propiedades de una relacion reflexiva son:

  • Simetria de la igualdad: intercambiar terminos
  • Transitividad de la igualdad: aplicar "transitividad" en igualaciones

• A la hora de armar las clases de equivalencia:

  • En conjuntos finitos basta con dalre un valor a uno de los elementos y despejar el otro, e ir iterando hasta obtener los valores de todas las clases.

  • En relaciones de divisibilidad se realiza el mismo procedimiento que en conjuntos finitos.

  • En relaciones en Reales se toma la expresion y se trata de llegar a formulas que representen las curvas que muestran las clases, en general son dos funciones lineales.

    • A la hora de armar las clases en este caso nos quedaran dos funciones (en general) la cantidad de clases es infinita, por lo que necesariamente van a estar definidas por las funciones.

      • En donde se crucen las funciones lineales se formara una unica clase de ese elemento.

    • Como las clases no se tienen que intersectar entre si por el Teorema Fundamental de las Relaciones de Equivalencia en este tipo de relaciones tendremos que limitar el conjunto de indices, que sera desde donde se crusan hasta el infinito.

      • Este conjunto de indices es el que pondremos en el conjunto cociente.

    • En resumen: primero armar las clases, seran dos, una la del elemento donde se intersectan las curvas, el resto son las funciones. Luego se arma el conjunto de indices, que sera desde el elemento donde se intersectan hasta el infinito. Finalmente se arma un conjunto cociente del estilo $\frac{\R}{S}=\{Cl(x)/x\in [m;\infin) \}$ siendo $[m;\infin)$ el conjunto de indices.

Unidad 5: Relaciones de Orden

$$R: A\to A \text{ es de } \textbf{orden}\begin{cases} \text{Reflexiva}\\ \text{Antisimetrica}\\ \text{Transitiva}\\ \end{cases}$$

Las relaciones de orden tambien se llaman de orden amplio

• En general estas relaciones son del estilo menor o igual $(\leq)$

• Las relaciones de orden se denotan con el simbolo "precede" $(\preceq)$

• Si existe una relacion de orden en un conjunto se dice que el conjunto esta ordenado $(A;\preceq)$

• Cualquier subconjunto de los naturales relacionado por la division, esta ordenado.

• Cualquier conjunto de divisores de un numero $n$ relacionado por la division, esta ordenado.

Diagrama de Hasse

Si se sabe que una relacion es de orden entonces se puede armar un Diagrama de Hasse. Un diagrama de hasse es un digrago de relaciones simplificado, sin bucles ni relaciones transitivas. Solo aristas directas.

Tambien se puede omitir las flechas pero para eso se tiene que hacer de forma vertical, siendo los elementos inferiores los que estan incluidos en en los elementos superiores.

Conjunto Totalmente Ordenado (TTO)

$\text{A esta TTO}\iff\forall x,y\in A: (x\preceq y \lor y\preceq x)$

• El Diagrama de Hasse de un conjunto tto es una cadena
• Aquellos elementos que no esten relacionados (osea que ninguno precede al otro) entonces estos se llaman elementos incomporables. Se denota $a//b$

Orden Reciproco

$\text{Sea }(A;\preceq)\quad\text{Sea } R:A\to A/ xRy\Leftrightarrow y\preceq x$

Orden usual del Producto

$\text{Sean }(A;\preceq_1)\text{ y }(B;\preceq_2)$

$$(x;y)R(z;t)\Leftrightarrow x\preceq_1z \land y\preceq_2 t$$

Elementos Notables de un Conjunto Ordenado

Maxiamal

$\text{Sea }(A;\preceq)$

$$m\in A \text{ es }\textbf{maximal}\text{ de } A \Leftrightarrow\forall x\in A: m\preceq x\rArr x = m$$

• Si el maximal es unico, se lo llama maximo o ultimo elemento.
• Es el que precede a todos los elementos de A.

Minimal

$\text{Sea }(A;\preceq)$

$$m\in A \text{ es }\textbf{minimal}\text{ de } A \Leftrightarrow\forall x\in A: x\preceq m\rArr x = m$$

• Si el minimal es unico, se lo llama minimo o primer elemento.
• Es el elemento que ningun otro lo precede.

Atomo

$\text{Sea }(A;\preceq)\text{ un conjunto ordenado con primer elemento } p$

$$m \in A \text{ es }\textbf{atomo}\text{ de } A \Leftrightarrow\forall x\in A: (x\preceq m \rArr x=m \lor x=p)$$

• Son los que estan inmediatamente despues del primer elemento.
  • Hay primer elemento cuando el diagrama de hasse converge en un solo elemento.

Conjunto Bien Ordenado

$\text{Sea }(A;\preceq)$

$$A \text{ esta Bien Ordenado } \Leftrightarrow \text{todo subconjunto de } A \text{ tiene } 1^{er}\text{ elemento}$$

• Entonces se deduce que en un conjunto de buen orden no puede haber elementos incomparables.

• $\text{Buen Orden} \rArr \text{Orden Total}$

Cotas Superiores e Inferiores

$\text{Sea } (A;\preceq)\text{ un conjunto ordenado y } \varnothing \neq B\sube A$

$$s\in A \text{ es } \textbf{cota superior} \text{ de } B \Leftrightarrow\forall x\in B:x\preceq s$$

$\text{Sea } (A;\preceq)\text{ un conjunto ordenado y } \varnothing \neq B\sube A$

$$i\in A \text{ es } \textbf{cota inferior} \text{ de } B \Leftrightarrow\forall x\in B:i\preceq x$$

• El conjunto de cotas superiores se llama Conjunto Mayorante.

• El conjunto de cotas inferiores se llama Conjunto Minorante.

• La menor de las cotas superiores, recibe el nombre de supremo.

• La mayor de las cotas inferiores, recibe el nombre de infimo.

• Si el supremo pertenece a B, se llama Maximo de B.

• Si el infimo pertenece a B, se llama Minimo de B.

Redes

$\text{Sea } (A;\preceq) \text{ un conjunto ordenado.}$

$$\text{Es }\textbf{Superior Semirreticulo} \iff \forall a,b \in A: \exist \text{ supremo}(a,b)$$

$\text{Sea } (A;\preceq) \text{ un conjunto ordenado.}$

$$\text{Es }\textbf{Inferior Semirreticulo} \iff \forall a,b \in A: \exist \text{ infimo}(a,b)$$

$\text{Sea } (A;\preceq) \text{ un conjunto ordenado.}$

$$(A;\preceq) \text{ es} \textbf{ Red} \iff \text{es superior e iferior semirreticulo}$$

Entre todo par de elementos debe existir supremo e infimo.

Entonces para que una relacion sea red, tiene que existir un supremo e infimo para cualquier par de elementos. En relacion a esto entonces, para verificar que esto se cumpla lo mas eficiente seria verificar si hay supremo e infimo entre los elementos incomparables, si es que tienen supremo e infimo en comun entonces la relacion es una red.

Propiedades

$\text{Si } a\preceq b \rArr \text{sup}(a,b) = b \quad y \quad \text{inf}(a,b) =a$

• Si un conjunto ordenado tiene mas de un maximal o mas de un minimal, no puede ser red porque los maximales no tendrian supremo o los minimales no tendrian infimo.
• Si un conjunto ordenado tiene solo un maximal y un solo minimal no necesariamente es red porque dos elementos incomparables pueden tener mas de un supremo o mas de un infimo, y esto no cumple con la propiedad de red.

Tabla

Propiedades para las operaciones de supremo e infimo:

$\text{Sea } (A;\preceq) \text{ una red. Las operaciones }\vee\text{ e }\land\text{ cumplen:}$